package leetcode.editor.cn.q1_300.q250;
//中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。 
//
// 
// 例如 arr = [2,3,4] 的中位数是 3 。 
// 例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。 
// 
//
// 实现 MedianFinder 类: 
//
// 
// MedianFinder() 初始化 MedianFinder 对象。 
// void addNum(int num) 将数据流中的整数 num 添加到数据结构中。 
// double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10⁻⁵ 以内的答案将被接受。 
// 
//
// 示例 1： 
//
// 
//输入
//["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
//[[], [1], [2], [], [3], []]
//输出
//[null, null, null, 1.5, null, 2.0]
//
//解释
//MedianFinder medianFinder = new MedianFinder();
//medianFinder.addNum(1);    // arr = [1]
//medianFinder.addNum(2);    // arr = [1, 2]
//medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
//medianFinder.addNum(3);    // arr[1, 2, 3]
//medianFinder.findMedian(); // return 2.0 
//
// 提示: 
//
// 
// -10⁵ <= num <= 10⁵ 
// 在调用 findMedian 之前，数据结构中至少有一个元素 
// 最多 5 * 10⁴ 次调用 addNum 和 findMedian 
// 
//
// 👍 850 👎 0

import java.util.PriorityQueue;

/**
 * 思路：
 * 两个堆，
 * 存储小于中间值的数，大顶堆
 * 存储大于中间值的数，小顶堆
 * <p>
 * 中间值一定是由两个数获得
 */
public class Q295_FindMedianFromDataStream {
    //leetcode submit region begin(Prohibit modification and deletion)
    class MedianFinder {

        // 存储小于中间值的数，大顶堆
        private PriorityQueue<Integer> smallQ;

        // 存储大于中间值的数，小顶堆
        private PriorityQueue<Integer> bigQ;

        public MedianFinder() {
            smallQ = new PriorityQueue<>((o1, o2) -> o2 - o1);
            bigQ = new PriorityQueue<>();
        }

        public void addNum(int num) {
            if (smallQ.isEmpty() || num < smallQ.peek()) {
                smallQ.add(num);

                if (smallQ.size() - bigQ.size() > 1) {
                    bigQ.add(smallQ.poll());
                }
            } else {
                bigQ.add(num);

                if (bigQ.size() > smallQ.size()) {
                    smallQ.add(bigQ.poll());
                }
            }
        }

        public double findMedian() {
            if (smallQ.size() > bigQ.size()) {
                return smallQ.peek();
            } else {
                return (smallQ.peek() + bigQ.peek()) / 2d;
            }
        }
    }

    /**
     * Your MedianFinder object will be instantiated and called as such:
     * MedianFinder obj = new MedianFinder();
     * obj.addNum(num);
     * double param_2 = obj.findMedian();
     */
    //leetcode submit region end(Prohibit modification and deletion)
    public static void main(String[] args) {
        MedianFinder medianFinder = new Q295_FindMedianFromDataStream().new MedianFinder();
        // TO TEST
        medianFinder.addNum(1);    // arr = [1]
        medianFinder.addNum(2);    // arr = [1, 2]
        System.out.println(medianFinder.findMedian()); // 返回 1.5 ((1 + 2) / 2)
        medianFinder.addNum(3);    // arr[1, 2, 3]
        System.out.println(medianFinder.findMedian()); // return 2.0
    }
}